package com.ai.zuochengyun.phase01.class06;

import java.util.*;

/**
 * 节点深度越大，排序越靠前
 */
public class Code05_TopologicalOrderDFS2 {

    /**
     * 如果x点走出的最大深度大于等于y，那么x的拓扑序排在y之前
     */
    public static List<DirectedGraphNode> topSort(List<DirectedGraphNode> graph) {
        Map<DirectedGraphNode, Record> order = new HashMap<>();
        for (DirectedGraphNode cur : graph) {
            process(cur, order);
        }

        // 按频次排序
        List<Record> array = new ArrayList<>();
        for (Record record : order.values()) {
            array.add(record);
        }
        array.sort(new MyComparator());

        List<DirectedGraphNode> ans = new ArrayList<>();
        for (Record record : array) {
            ans.add(record.node);
        }
        return ans;
    }

    /**
     * 返回cur点所到之处的点的频次
     *
     * @param cur   当前来到的点
     * @param order
     */
    private static Record process(DirectedGraphNode cur, Map<DirectedGraphNode, Record> order) {
        if (order.containsKey(cur)) {
            return order.get(cur);
        }

        int deep = 0;
        for (DirectedGraphNode next : cur.neighbors) {
            // 找到所有邻居中深度最大的
            deep = Math.max(deep, process(next, order).deep);
        }

        // 自己的深度是最大邻居深度值+1
        Record ans = new Record(cur, deep + 1);
        // 放进缓存
        order.put(cur, ans);
        return ans;
    }

    /**
     * 倒序排序  深度越深的拓扑序越靠前
     */
    private static class MyComparator implements Comparator<Record> {

        @Override
        public int compare(Record o1, Record o2) {
            // 返回负数，第一个参数排前面，返回正数，第二个参数排前面
            return o2.deep - o1.deep;
        }
    }

    private static class Record {
        public DirectedGraphNode node;

        /**
         * 节点的最大深度
         */
        public int deep;

        public Record(DirectedGraphNode node, int deep) {
            this.node = node;
            this.deep = deep;
        }
    }
}
